[AA] Fixed-Point Amplitude Amplification

2023 iThome 鐵人賽

DAY 8

自我挑戰組

不嚴謹的量子計算雜談系列第 8 篇

15th鐵人賽量子計算

bwl

2023-09-17 10:09:38

202 瀏覽

分享至

還記得兩天前談到的舒芙蕾問題 (soufflé problem) 嗎？旋轉的次數 $k$ 如果太小，AA 的效果不明顯； $k$ 如果太大，卻可能轉過頭了 (正如舒芙蕾必須烘焙地恰如其分)。這個問題該如何解決？

回想起來，經過 $k$ 次旋轉之後，我們的振幅從 $\sqrt{p} = \sin\theta$ 變成 $\sin((2k+1)\theta)$ ，而我們希望 $\sin((2k+1)\theta)\approx 1$ ，也就是 $(2k+1)\theta \approx \pi/2$ 。可以看出來， $k$ 值的選擇取決於 $p$ ！倘若我們事先知道 $p$ ，問題圓滿解決！但現實經常不從人願。如果 $p$ 未知，或許我們可以猜看看： $k=1$ 時表現如何？ $k=2$ 、 $k=4$ 、 $k=8$ 呢？透過指數增加猜測的 $k$ ，我們可以快速估計適當的 $k$ 值。(有多快？當 $\theta$ 很小， $\sqrt{p}=\sin\theta\approx \theta$ ，於是猜 $O\big(\log(1/\sqrt{p})\big)$ 次即可。)

雖然多猜幾次可以解決問題，但有沒有一種演算法，不會發生「轉超過」的情形呢？沒錯！就是今天要介紹的 fixed-point AA。Grover 在 2005 年提出了 fixed-point search (search 和 AA 是同一件事) (可以稱為 Grover’s π/3-algorithm)，雖然解決了舒芙蕾問題，但是卻犧牲了得來不易的二次加速 (quadratic speedup；從 $O(\sqrt{N})$ 變回 $O(N)$ 了)！